19.删除链表的倒数第 N 个节点

LeetCode 原题链接 image.png

实现思路

  • 定义一个 dummy 节点指向 head，这样可以方便地处理删除头节点的情况。
  • 定义两个指针 slow 和 fast，slow 初始化为 dummy，fast 初始化为 dummy。
  • fast 先向前移动 n 步，这样 slow 和 fast 之间就有 n 个节点的距离。
  • 然后同时移动 slow 和 fast，直到 fast 到达链表的末尾，此时 slow 的下一个节点就是需要删除的节点。
  • 将 slow 的 next 指向 slow 的 next 的 next，即可删除倒数第 n 个节点。

代码实现

var removeNthFromEnd = function (head, n) {
  // 虚拟头节点可以统一处理“删除头节点”的情况。
  // 例如链表 [1] 删除倒数第 1 个节点时，最终只需修改 dummy.next。
  const dummy = new ListNode(0, head);

  // slow 最终要停在待删除节点的前一个节点。
  let slow = dummy;

  // fast 用来与 slow 保持固定距离。
  let fast = dummy;

  // fast 先走 n 步。
  // 此后 fast 与 slow 之间相隔 n 条边：
  // slow --1--> ... --n--> fast
  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }

  // fast 停在尾节点时，slow 恰好停在待删除节点的前一个节点。
  // 所以判断的是 fast.next !== null，而不是 fast !== null。
  while (fast.next !== null) {
    slow = slow.next;
    fast = fast.next;
  }

  // 跳过 slow 的下一个节点，即删除倒数第 n 个节点。
  slow.next = slow.next.next;

  // dummy.next 是删除操作完成后的真正头节点。
  return dummy.next;
};

为什么循环条件是 fast.next !== null？

关键目标不是让 slow 停在待删除节点上，而是让它停在待删除节点的前一个节点。只有这样才能执行：

slow.next = slow.next.next;

假设链表是：

dummy → 1 → 2 → 3 → 4 → 5 → null

删除倒数第 2 个节点，也就是删除 4。

1. fast 先走两步

slow 和 fast 都从 dummy 出发，fast 先走 n = 2 步：

slow
  ↓
dummy → 1 → 2 → 3 → 4 → 5 → null
            ↑
           fast

此时 slow 在 dummy，fast 在节点 2。

2. 两个指针同时移动

只要 fast 后面还有节点，就让两个指针一起前进：

移动次数slow 所在节点fast 所在节点fast.next
0dummy23
1134
2245
335null，停止

循环停止时：

              slow       待删除
                ↓           ↓
dummy → 1 → 2 → 3 → 4 → 5 → null
                            ↑
                           fast

fast 位于尾节点 5，slow 位于节点 3，正好是待删除节点 4 的前一个节点。

因此可以执行：

slow.next = slow.next.next;

把 3 → 4 → 5 改成 3 → 5。

如果写成 fast !== null 会怎样？

如果循环条件改成：

while (fast !== null) {
  slow = slow.next;
  fast = fast.next;
}

当 fast 位于节点 5 时，条件仍然成立，两个指针会再移动一次：

fast = null
slow = 节点 4

此时 slow 已经停在待删除节点 4 上，而不是它的前一个节点。继续执行：

slow.next = slow.next.next;

删除的将是节点 5，结果就错了。

可以记住这组搭配：

fast 先走 n 步   + while (fast.next !== null)
                → slow 停在待删除节点的前一个节点

另一种同样正确的写法是让 fast 先走 n + 1 步，然后使用 while (fast !== null)。两种写法的本质相同：始终让 slow 最终停在待删除节点的前一个节点。